1054. 距离相等的条形码【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计数 + 间隔放置

1. 📝 题目描述

• leetcode

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

---

示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

输入：barcodes = [1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

---

提示：

• 1 <= barcodes.length <= 10000
• 1 <= barcodes[i] <= 10000

2. 🎯 s.1 - 计数 + 间隔放置

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} barcodes
 * @return {number[]}
 */
var rearrangeBarcodes = function (barcodes) {
  const count = new Map()
  for (const b of barcodes) count.set(b, (count.get(b) || 0) + 1)
  const sorted = [...count.entries()].sort((a, b) => b[1] - a[1])
  const res = new Array(barcodes.length)
  let idx = 0
  for (const [val, cnt] of sorted) {
    for (let i = 0; i < cnt; i++) {
      res[idx] = val
      idx += 2
      if (idx >= barcodes.length) idx = 1
    }
  }
  return res
}

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(n)$，计数和结果数组

算法思路：

• 统计每个条形码的出现次数，按频率降序排序
• 先放偶数位置，再放奇数位置，确保相邻元素不同
• 优先放置频率最高的元素，保证不会出现相邻重复